//给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单 
//blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。 
//
// 优化你的算法，使它最小化调用语言 内置 随机函数的次数。 
//
// 实现 Solution 类: 
//
// 
// Solution(int n, int[] blacklist) 初始化整数 n 和被加入黑名单 blacklist 的整数 
// int pick() 返回一个范围为 [0, n - 1] 且不在黑名单 blacklist 中的随机整数 
// 
//
// 
//
// 示例 1： 
//
// 
//输入
//["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
//[[7, [2, 3, 5]], [], [], [], [], [], [], []]
//输出
//[null, 0, 4, 1, 6, 1, 0, 4]
//
//解释
//Solution solution = new Solution(7, [2, 3, 5]);
//solution.pick(); // 返回0，任何[0,1,4,6]的整数都可以。注意，对于每一个pick的调用，
//                 // 0、1、4和6的返回概率必须相等(即概率为1/4)。
//solution.pick(); // 返回 4
//solution.pick(); // 返回 1
//solution.pick(); // 返回 6
//solution.pick(); // 返回 1
//solution.pick(); // 返回 0
//solution.pick(); // 返回 4
// 
//
// 
//
// 提示: 
//
// 
// 1 <= n <= 10⁹ 
// 0 <= blacklist.length <= min(10⁵, n - 1) 
// 0 <= blacklist[i] < n 
// blacklist 中所有值都 不同 
// pick 最多被调用 2 * 10⁴ 次 
// 
// Related Topics 哈希表 数学 二分查找 排序 随机化 👍 144 👎 0

package leetcode.editor.cn;

import java.util.*;

public class _710_RandomPickWithBlacklist {
    public static void main(String[] args) {
//        int n = 7;
//        int[] blacklist = {2, 3, 5};
        int n = 1000000000;
        int[] blacklist = {640145908};
//        List<Integer> list = new LinkedList<>();
//        list.add(1);
//        list.add(2);
//        list.add(3);
//        System.out.println(list.get(1));
        Solution solution = new _710_RandomPickWithBlacklist().new Solution(n, blacklist);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < 60000; i++) {
            int pick = solution.pick();
            map.put(pick, map.getOrDefault(pick, 0) + 1);
        }
        for (Integer integer : map.keySet()) {
            System.out.println(integer + " : " + map.get(integer));
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 我发现只要是遍历了n的数组，就会超时，所以
     */
    class Solution {
        private Map<Integer, Integer> map;
        private Random random;
        private int n;
        private int[] blacklist;

        public Solution(int n, int[] blacklist) {
            random = new Random();
            int m = blacklist.length;
            this.n = n;
            this.blacklist = blacklist;
            Set<Integer> set = new HashSet<>();
            map = new HashMap<>();

            for (int num : blacklist) {
                if (num >= n - m) {
                    set.add(num);
                }
            }

            int index = 0;
            for (int num : blacklist) {
                if (num < n - m) {
                    while (set.contains(n - m + index)) {
                        index++;
                    }
                    map.put(num, n - m + index++);
                }
            }
        }

        public int pick() {
            int x = random.nextInt(n - blacklist.length);
            return map.getOrDefault(x, x);
        }
    }

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(n, blacklist);
 * int param_1 = obj.pick();
 */
//leetcode submit region end(Prohibit modification and deletion)

}